package com.aqie.medium.linkedlist;


import com.aqie.easy.structure.ListNode;

/**
 * 328 将奇数节点 和 偶数节点排在一起
 */
public class OddEvenList {
    /**
     * todo
     * 遍历链表的同时将链表分为奇数链表和偶数链表，然后拼接起来
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;

        ListNode odd = head;
        ListNode even = head.next;

        ListNode node = head.next.next;
        ListNode headEven = even;

        // 区分奇偶 链表
        while (node != null && node.next != null){
            odd.next = node;
            even.next = node.next;
            // 防止最后一个奇数节点 接到偶数节点
            node.next = null;

            node = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        // 如果最后一个节点是奇数节点 ，额外处理
        if (node != null){
            odd.next = node;
            even.next = null;
            odd = node;
        }

        // 拼接两个链表
        odd.next = headEven;
        return head;
    }

    /**
     * 奇偶链表
     * @param head
     * @return
     */
    public ListNode oddEvenList2(ListNode head){
        if (head == null) return null;
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

    /**
     * 三指针
     */
    public ListNode oddEvenList3(ListNode head){
        if (head == null) return null;

        ListNode even = head.next;
        ListNode oddtmp = head;
        ListNode eventmp = even;
        while (oddtmp != null && eventmp != null && eventmp.next != null){
            oddtmp.next = eventmp.next;
            oddtmp = oddtmp.next;
            eventmp.next = oddtmp.next;
            eventmp = eventmp.next;
        }

        if (eventmp == null) oddtmp.next = even;
        else {
            eventmp.next = null;
            oddtmp.next = even;
        }
        return head;
    }

}
